package kyssion.introductionToAlgorithms.chapter_02;

import kyssion.leetcode.util.ShowUtil;

public class Alorithms002_归并排序 {

    public static void main(String[] args) {
        int[] iii = new int[]{
                2, 3, 4, 2, 1, 2, 3, 4, 4
        };
        new Alorithms002_归并排序().sort(iii, 0, iii.length - 1);
        ShowUtil.showArr(iii);
    }


    public void sort(int[] arr, int start, int end) {
        if (start < end) {
            int midle = (end + start) >> 1;
            sort(arr, start, midle);
            sort(arr, midle + 1, end);
            merge(arr, start, midle, end);
        }
    }

    private void merge(int[] arr, int start, int midle, int end) {
        if (start >= end) {
            return;
        }
        //start = 0 end = 1  midle = 0
        int n1 = midle - start + 1;
        int n2 = end - midle;
        int[] left = new int[n1 + 1];
        int[] right = new int[n2 + 1];
        for (int a = 0; a < n1; a++) {
            left[a] = arr[start + a];
        }
        for (int a = 0; a < n2; a++) {
            right[a] = arr[midle + a + 1];
        }
        left[left.length - 1] = Integer.MAX_VALUE;
        right[right.length - 1] = Integer.MAX_VALUE;
        n1 = 0;
        n2 = 0;
        for (int a = start; a <= end; a++) {
            if (left[n1] < right[n2]) {
                arr[a] = left[n1];
                n1++;
            } else {
                arr[a] = right[n2];
                n2++;
            }
        }
    }
}
